#include <stdio.h>
#include "algo_mergeSort.h"

#define numElement 10

// an auxilarary function for merging two sorted halves
void merge(int a[], int startIndex, int midIndex, int endIndex) {
	// creat temp array with the size of a
	int length = endIndex - startIndex + 1;
	int *tmp = new int[length];

	int i = startIndex;
	int j = midIndex + 1;
	int index = 0;
	while (i <= midIndex && j <= endIndex) {
		if (a[i] < a[j]) {
			tmp[index] = a[i];
			i++;
		} else {
			tmp[index] = a[j];
			j++;
		}
		index++;
	}

	// copy the rest of the array
	if (i > midIndex) {
		while (j <= endIndex) {
			tmp[index] = a[j];
			index++;
			j++;
		}
	}
	else if (j > endIndex) {
		while (i <= midIndex) {
			tmp[index] = a[i];
			index++;
			i++;
		}		
	}
	// copy tmp array back to a
	for (i = 0; i < length; i++)
		a[startIndex+i] = tmp[i];

	delete[] tmp;
}

void mergeSort(int a[], int startIndex, int endIndex) {
	if (startIndex >= endIndex)
		return;
	int midIndex = (startIndex + endIndex)/2;
	// merge sort the first half
	mergeSort(a, startIndex, midIndex);
	// merge sort the second half
	mergeSort(a, midIndex+1, endIndex);
	// merge both sorted halves
	merge(a, startIndex, midIndex, endIndex);
}

void test_algo_mergeSort() {
	int data[numElement] = { 12, 1, 3, 6, 9, 8, 2, 7, 10, 15 };

	printf("Before sorting.\n");
	for (int i = 0; i < numElement; i++) {
		printf("%d", data[i]);
		if ( i < numElement - 1 )
			printf(", ");
		else
			printf("\n");
	}
	printf("\n");
	mergeSort(data, 0, numElement-1);
	printf("After merge sorting.\n");
	for (int i = 0; i < numElement; i++) {
		printf("%d", data[i]);
		if ( i < numElement - 1 )
			printf(", ");
		else
			printf("\n");
	}
}
